package com.hubu.tree;
import com.hubu.tree.util.Comparator;
import com.hubu.tree.util.Visitor;
public class BinarySearchTree<T> extends AbstractTree<T> implements Tree<T> {
    public BinarySearchTree(Comparator<T> comparator, Visitor<T> visitor) {
        super(comparator, visitor);
    }
    @Override
    public T add(T value) {
        if(root==null){
            root=createNode(value,null,null);
            afterAdd(root);
            return null;
        }
        TreeNode<T> parent=null;
        TreeNode<T> current=root;
        int compare=0;
        while(current!=null) {
            parent = current;
            compare = compare(value, current.getValue());
            if (compare > 0) {
                current = current.rightOf();
            } else if (compare < 0) {
                current = current.leftOf();
            } else {
                T oldValue = current.getValue();
                current.setValue(value);
                return oldValue;
            }
        }
        TreeNode<T> newNode=createNode(value,null,null);
        if(compare>0){
            parent.setRight(newNode);
        }
        else{
            parent.setLeft(newNode);
        }
        connectParent(parent,newNode);
        afterAdd(newNode);
        return null;
        //变化部分
    }

    //空方法 留给子类去实现
    public  void afterAdd(TreeNode<T> node){

    }
    /**
     * 变化的部分隔离出来让子类能够重写
     */
    public void connectParent(TreeNode<T> parent, TreeNode<T> newNode){
        ((BinarySearchTreeNode<T>)newNode).parent=parent;
    }
    @Override
    public TreeNode<T> createNode(T value, TreeNode<T> left, TreeNode<T> right) {
        TreeNode<T> node=new BinarySearchTreeNode<>(value,left,right,null);
        return node;
    }
    public static class BinarySearchTreeNode<T> extends Node<T>{
        protected TreeNode<T> parent;
        public BinarySearchTreeNode(T value, TreeNode<T>left, TreeNode<T> right,TreeNode<T> parent) {
            super(value, left, right);
            this.parent=parent;
        }
    }
}
